package algorithm.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class SolutionAll {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public void main(String[] args) {
        TreeNode node = new TreeNode();
        TreeNode node2 = new TreeNode(3);
        TreeNode node3 = new TreeNode(3, node2,node);
        System.out.printf(node3.toString());

    }
/*

    递归三部曲
    1 确定递归函数的参数和返回值
    2 确定终止条件
    3 确定单层递归的逻辑
*/

    class Solution513 {
//       目标： 该二叉树的 最底层 最左边 节点的值。
        //深度优先搜索
/*
    思路：重点是
    nowHeight 当前遍历到的节点所处的高度。
    recordMaxHeight 记录最大深度
    val 记录 最大深度 maxHeight时，最左节点的数值。

     !!! 先遍历当前节点的左子树，再遍历当前节点的右子树。!!!
     注意：因为先遍历左子树，然后再遍历右子树，所以对同一高度的所有节点，最左节点肯定是最先被遍历到的。
     1、当前节点的左子树，
     当前高度 nowHeight < recordMaxHeight, 最左值不用变。
     当前高度 nowHeight > recordMaxHeight, 将 curVal设置为当前结点的值。（不用急着设置为结点的左节点值，因为先遍历的左子树）

     2、再遍历当前节点的右子树。
     当前高度 nowHeight < recordMaxHeight, 最左值不会是当前，不用变。
     当前高度 nowHeight > recordMaxHeight, 将 curVal设置为当前结点的值。（不用急着设置为结点的左节点值，因为先遍历的左子树，再说左子树也可能为null）

*/
    int recordMaxHeight =0; //初始化
    int val= 0;

        public int findBottomLeftValue(TreeNode root) {

            dfs(root,0); //作用：更新最左节点的数值。
            return val;
        }
//    1 确定递归函数的参数和返回值：节点，当前层高。
//
//    2 确定终止条件 ：root =null

    public void dfs(TreeNode root, int nowHeight){
        if(root == null){
            return ;
        }
//    3 确定单层递归的逻辑  高度、更新cul
        nowHeight++;//高度记得一定要更新呀。

        dfs(root.left, nowHeight); //可以判断root.left!=null，但下次递归就自动判断了。
        dfs(root.right, nowHeight); //可以判断root.right!=null，但下次递归就自动判断了。
        if(nowHeight > recordMaxHeight){
            recordMaxHeight = nowHeight;  //注意要更新：最大深度!!!
            val=root.val; //看做是当前高度的节点值。（注意：最左节点是先被遍历到的，结果是符合题意的）
//也可以判断root.left不为空，是root.left.val; 为空就等于root.val。但root.left因为已经被递归了，不用再多次一举判断了。
        }

    }

    }

class Solution513_2 {
/*  目标： 该二叉树的 最底层 最左边 节点的值。
广度优先搜索：从右到左遍历每一层的节点，所最后一个节点的值就是最底层最左边节点的值。
结构：放入队列 ,先进先出。
*/
    public int findBottomLeftValue(TreeNode root) {
        int res = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            //处理。先右边
            TreeNode node = queue.poll(); //队列移头
            if(node.right !=null){
                queue.offer(node.right);
            }
            if(node.left!=null){
                queue.offer(node.left);
            }
//queue在减少。
// 判断 queue.size() == 1错误，因为如果root是1个，上面的操作就没有offer进去过。
            if(queue.isEmpty()){
                res = node.val;
            }
        }

        return res;
    }
}





}